MozartV1, Main, Exploration, bibRecord, 001B61

CP(Graph): Introducing a Graph Computation Domain in Constraint Programming

Identifieur interne : 001B61 ( Main/Exploration ); précédent : 001B60; suivant : 001B62

CP(Graph): Introducing a Graph Computation Domain in Constraint Programming

Auteurs : Gregoire Dooms [Belgique] ; Yves Deville [Belgique] ; Pierre Dupont [Belgique]

Source :

Lecture Notes in Computer Science [ 0302-9743 ] ; 2005.

RBID : ISTEX:50FE95E300534AEED6B097B05C8068C7308CC10A

Abstract

Abstract: In an increasing number of domains such as bioinformatics, combinatorial graph problems arise. We propose a novel way to solve these problems, mainly those that can be translated to constrained subgraph finding. Our approach extends constraint programming by introducing CP(Graph), a new computation domain focused on graphs including a new type of variable: graph domain variables as well as constraints over these variables and their propagators. These constraints are subdivided into kernel constraints and additional constraints formulated as networks of kernel constraints. For some of these constraints a dedicated global constraint and its associated propagator are sketched. CP(Graph) is integrated with finite domain and finite sets computation domains, allowing the combining of constraints of these domains with graph constraints. A prototype of CP(Graph) built over finite domains and finite sets in Oz is presented. And we show that a problem of biochemical network analysis can be very simply described and solved within CP(Graph).

Url:

https://api.istex.fr/document/50FE95E300534AEED6B097B05C8068C7308CC10A/fulltext/pdf

DOI: 10.1007/11564751_18

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Istex, to step Corpus: 000362
to stream Istex, to step Curation: 000282
to stream Istex, to step Checkpoint: 001493
to stream Main, to step Merge: 001B90
to stream Main, to step Curation: 001B61

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">CP(Graph): Introducing a Graph Computation Domain in Constraint Programming</title>
<author><name sortKey="Dooms, Gregoire" sort="Dooms, Gregoire" uniqKey="Dooms G" first="Gregoire" last="Dooms">Gregoire Dooms</name>
</author>
<author><name sortKey="Deville, Yves" sort="Deville, Yves" uniqKey="Deville Y" first="Yves" last="Deville">Yves Deville</name>
</author>
<author><name sortKey="Dupont, Pierre" sort="Dupont, Pierre" uniqKey="Dupont P" first="Pierre" last="Dupont">Pierre Dupont</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:50FE95E300534AEED6B097B05C8068C7308CC10A</idno>
<date when="2005" year="2005">2005</date>
<idno type="doi">10.1007/11564751_18</idno>
<idno type="url">https://api.istex.fr/document/50FE95E300534AEED6B097B05C8068C7308CC10A/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000362</idno>
<idno type="wicri:Area/Istex/Curation">000282</idno>
<idno type="wicri:Area/Istex/Checkpoint">001493</idno>
<idno type="wicri:doubleKey">0302-9743:2005:Dooms G:cp:graph:introducing</idno>
<idno type="wicri:Area/Main/Merge">001B90</idno>
<idno type="wicri:Area/Main/Curation">001B61</idno>
<idno type="wicri:Area/Main/Exploration">001B61</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">CP(Graph): Introducing a Graph Computation Domain in Constraint Programming</title>
<author><name sortKey="Dooms, Gregoire" sort="Dooms, Gregoire" uniqKey="Dooms G" first="Gregoire" last="Dooms">Gregoire Dooms</name>
<affiliation wicri:level="4"><country xml:lang="fr">Belgique</country>
<wicri:regionArea>Department of Computing Science and Engineering, Université catholique de Louvain, B-1348, Louvain-la-Neuve</wicri:regionArea>
<orgName type="university">Université catholique de Louvain</orgName>
<placeName><settlement type="city">Louvain-la-Neuve</settlement>
<region type="region" nuts="1">Région wallonne</region>
<region type="province" nuts="1">Province du Brabant wallon</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Belgique</country>
</affiliation>
</author>
<author><name sortKey="Deville, Yves" sort="Deville, Yves" uniqKey="Deville Y" first="Yves" last="Deville">Yves Deville</name>
<affiliation wicri:level="4"><country xml:lang="fr">Belgique</country>
<wicri:regionArea>Department of Computing Science and Engineering, Université catholique de Louvain, B-1348, Louvain-la-Neuve</wicri:regionArea>
<orgName type="university">Université catholique de Louvain</orgName>
<placeName><settlement type="city">Louvain-la-Neuve</settlement>
<region type="region" nuts="1">Région wallonne</region>
<region type="province" nuts="1">Province du Brabant wallon</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Belgique</country>
</affiliation>
</author>
<author><name sortKey="Dupont, Pierre" sort="Dupont, Pierre" uniqKey="Dupont P" first="Pierre" last="Dupont">Pierre Dupont</name>
<affiliation wicri:level="4"><country xml:lang="fr">Belgique</country>
<wicri:regionArea>Department of Computing Science and Engineering, Université catholique de Louvain, B-1348, Louvain-la-Neuve</wicri:regionArea>
<orgName type="university">Université catholique de Louvain</orgName>
<placeName><settlement type="city">Louvain-la-Neuve</settlement>
<region type="region" nuts="1">Région wallonne</region>
<region type="province" nuts="1">Province du Brabant wallon</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Belgique</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2005</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
</series>
<idno type="istex">50FE95E300534AEED6B097B05C8068C7308CC10A</idno>
<idno type="DOI">10.1007/11564751_18</idno>
<idno type="ChapterID">Chap18</idno>
<idno type="ChapterID">18</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: In an increasing number of domains such as bioinformatics, combinatorial graph problems arise. We propose a novel way to solve these problems, mainly those that can be translated to constrained subgraph finding. Our approach extends constraint programming by introducing CP(Graph), a new computation domain focused on graphs including a new type of variable: graph domain variables as well as constraints over these variables and their propagators. These constraints are subdivided into kernel constraints and additional constraints formulated as networks of kernel constraints. For some of these constraints a dedicated global constraint and its associated propagator are sketched. CP(Graph) is integrated with finite domain and finite sets computation domains, allowing the combining of constraints of these domains with graph constraints. A prototype of CP(Graph) built over finite domains and finite sets in Oz is presented. And we show that a problem of biochemical network analysis can be very simply described and solved within CP(Graph).</div>
</front>
</TEI>
<affiliations><list><country><li>Belgique</li>
</country>
<region><li>Province du Brabant wallon</li>
<li>Région wallonne</li>
</region>
<settlement><li>Louvain-la-Neuve</li>
</settlement>
<orgName><li>Université catholique de Louvain</li>
</orgName>
</list>
<tree><country name="Belgique"><region name="Région wallonne"><name sortKey="Dooms, Gregoire" sort="Dooms, Gregoire" uniqKey="Dooms G" first="Gregoire" last="Dooms">Gregoire Dooms</name>
</region>
<name sortKey="Deville, Yves" sort="Deville, Yves" uniqKey="Deville Y" first="Yves" last="Deville">Yves Deville</name>
<name sortKey="Deville, Yves" sort="Deville, Yves" uniqKey="Deville Y" first="Yves" last="Deville">Yves Deville</name>
<name sortKey="Dooms, Gregoire" sort="Dooms, Gregoire" uniqKey="Dooms G" first="Gregoire" last="Dooms">Gregoire Dooms</name>
<name sortKey="Dupont, Pierre" sort="Dupont, Pierre" uniqKey="Dupont P" first="Pierre" last="Dupont">Pierre Dupont</name>
<name sortKey="Dupont, Pierre" sort="Dupont, Pierre" uniqKey="Dupont P" first="Pierre" last="Dupont">Pierre Dupont</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/MozartV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001B61 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001B61 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Musique
   |area=    MozartV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:50FE95E300534AEED6B097B05C8068C7308CC10A
   |texte=   CP(Graph): Introducing a Graph Computation Domain in Constraint Programming
}}

This area was generated with Dilib version V0.6.20.
Data generation: Sun Apr 10 15:06:14 2016. Site generation: Tue Feb 7 15:40:35 2023

	Serveur d'exploration sur Mozart
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Mozart

CP(Graph): Introducing a Graph Computation Domain in Constraint Programming

CP(Graph): Introducing a Graph Computation Domain in Constraint Programming

Source :

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri